package com.tcm.day05;

import com.tcm.day03.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 合并 K 个升序链表
 * https://leetcode.cn/problems/merge-k-sorted-lists/description/?envType=problem-list-v2&envId=linked-list
 */
public class Code04_CombineMultiLinkedList {

    public static class CombineMultiLinkedList {
        public ListNode mergeKLists(ListNode[] lists) {

            if (null == lists || lists.length == 0) return null;

            PriorityQueue<ListNode> dump = new PriorityQueue(new Comparator<ListNode>() {
                @Override
                public int compare(ListNode node1, ListNode node2) {
                    return node1.val - node2.val;
                }
            });
            for (ListNode node : lists) {
                dump.add(node);
            }

            ListNode head = dump.poll();
            ListNode prev = head;
            if(head.next != null) {
                dump.add(head.next);
            }

            while (!dump.isEmpty()) {
                ListNode next = dump.poll();
                if (next.next != null) dump.add(next.next);

                prev.next = next;
                prev = next;
            }

            return head;
        }
    }

}
